/**
 * 约瑟夫问题，单循环链表的一个应用
 * @Auther Jun jie Yi
 * @Date 17:31 2021/7/5
 */
public class Josephu {
    public static void main(String[] args) {
        //测试环形链表和遍历是否可用
        CircleSingleLinkedList circleSingleLinkedList = new Josephu().new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(25);
        circleSingleLinkedList.showBoy();
        //测试小孩出圈
        circleSingleLinkedList.outBoy(1, 2, 25);
    }
    //创建一个环形的单项链表
    class CircleSingleLinkedList {
        //创建一个 first 结点，当前没有编号
        private Boy first = new Boy(-1);
        //添加小孩结点，构成一个环形链表
        public void addBoy(int nums) {
            if(nums < 1) {
                System.out.println("nums的值不正确！");
                return;
            }
            Boy curBoy = null; //辅助指针
            //使用for循环创建一个环形链表
            for (int i = 1; i <= nums; i++) {
                //根据编号，创建小孩结点
                Boy boy = new Boy(i);
                //如果时第一个小孩
                if(i == 1) {
                    first = boy;
                    first.next = first;
                    curBoy = first;
                } else {
                    //这里采用的是尾插法
                    curBoy.next = boy;
                    boy.next = first;
                    curBoy = boy;
                }
            }
        }
        //遍历当前的循环链表
        public void showBoy() {
            //判断链表是否为空
            if(first == null) {
                System.out.println("没有任何小孩！");
                return;
            }
            //因为first不能动我们要使用辅助指针
            Boy curBoy = first;
            while(true) {
                System.out.printf("小孩的编号 %d\n", curBoy.no);
                curBoy = curBoy.next;
                if(curBoy == first) break;
            }
        }
        /**
         * 根据用户的输入，计算出小孩出圈的一个顺序
         * @param startNo 表示从第几个小孩开始数数
         * @param countNum 表示数几下
         * @param nums 表示最初有多少个小孩在圈中
         */
        public void outBoy(int startNo, int countNum, int nums) {
            //校验数据
            if(first == null || startNo < 1 || startNo > nums) System.out.println("参数输入有误");
            //创建辅助指针
            Boy helper = first;
            //这个循环让其指向最后一个结点
            while(true) {
                if(helper.next == first) break;
                helper = helper.next;
            }
            //先移动到报数位置
            for (int j = 0; j < startNo - 1; j++) {
                first = first.next;
                helper = helper.next;
            }
            //移动到报数次数删除结点，直到圈中只有一个结点
            while(true) {
                if(helper == first) break;
                for (int i = 0; i < countNum - 1; i++) {
                    first = first.next;
                    helper = helper.next;
                }
                //这时first指向的结点就是要出圈的结点
                System.out.printf("小孩 %d 出圈\n", first.no);
                //删除结点
                first = first.next;
                helper.next = first;
            }
            System.out.printf("最后留在圈中结点的小孩是 %d \n", first.no);
        }
    }

    //创建一个 Boy 类，表示一个结点
    class Boy {
        private int no; //编号
        private Boy next; //指向下一个结点，默认null
        public Boy(int no) {
            this.no = no;
        }
    }
}
